package com.jp.algorithm;

public class MidNum {

    public static int findMid(int[] nums1, int[] nums2) {

        int m = nums1.length - 1;
        int n = nums2.length - 1;
        if(m==0 && n==0)
            return -1;
        int k = (m + n) / 2;
        if ((m + n) % 2 == 1) {
            return getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, k);
        } else {
            int a=getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, k);
            int b=getKth(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, k+1);
            return  (a+b)/2;
        }
    }

    public static int getKth(int[] nums1, int l1, int h1, int[] nums2, int l2, int h2, int k) {
        int m = h1 - l1 + 1;
        int n = h2 - l2 + 1;

        if (m > n) {
            getKth(nums2, l2, h2, nums1, l1, h1, k);
        }

        if (m == 0) {
            return nums2[l2 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[l1], nums2[l2]);
        }

        int a = Math.min(k / 2, m);
        int b = k - a;
        int va = nums1[l1 + a - 1];
        int vb = nums2[l2 + b - 1];
        if (va == vb) {
            return va;
        } else if (va < vb) {
            return getKth(nums1, l1 + a, h1, nums2, l2, l2 + b - 1, k - a);
        } else {
            return getKth(nums1, l1, l1 + a - 1, nums2, l2 + b, h2, k - b);
        }
    }
}
